We still need to demonstrate that the properties in P AC-Bayes analysis hold for both the margin operator and the robust margin operator. Then we complete the proof of Lemma 6.1. The proof of Lemma 7.1 and 7.2 is similar. We provide the proof of Lemma 7.2 below. Lemma 7.1 follows the proof of Lemma 7.2 by replacing the robust margin operator by the margin Since the above bound holds for any x in the domain X, we can get the following a.s.: R The second inequality is the tail bound above.

We still need to demonstrate that the properties in P AC-Bayes analysis hold for both the margin operator and the robust margin operator. Then we complete the proof of Lemma 6.1. The proof of Lemma 7.1 and 7.2 is similar. We provide the proof of Lemma 7.2 below. Lemma 7.1 follows the proof of Lemma 7.2 by replacing the robust margin operator by the margin Since the above bound holds for any x in the domain X, we can get the following a.s.: R The second inequality is the tail bound above.

Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversarially robust generalization has a pivotal role in establishing effective defense algorithms against adversarial attacks. In this paper, we contribute by providing adversarially robust generalization bounds for two kinds of popular GNNs, graph convolutional network (GCN) and message passing graph neural network, using the PAC-Bayesian framework. Our result reveals that spectral norm of the diffusion matrix on the graph and spectral norm of the weights as well as the perturbation factor govern the robust generalization bounds of both models. Our bounds are nontrivial generalizations of the results developed in (Liao et al., 2020) from the standard setting to adversarial setting while avoiding exponential dependence of the maximum node degree. As corollaries, we derive better PAC-Bayesian robust generalization bounds for GCN in the standard setting, which improve the bounds in (Liao et al., 2020) by avoiding exponential dependence on the maximum node degree.

Deep neural networks (DNNs) are vulnerable to adversarial attacks. It is found empirically that adversarially robust generalization is crucial in establishing defense algorithms against adversarial attacks. Therefore, it is interesting to study the theoretical guarantee of robust generalization. This paper focuses on norm-based complexity, based on a PAC-Bayes approach (Neyshabur et al., 2017). The main challenge lies in extending the key ingredient, which is a weight perturbation bound in standard settings, to the robust settings. Existing attempts heavily rely on additional strong assumptions, leading to loose bounds. In this paper, we address this issue and provide a spectrally-normalized robust generalization bound for DNNs. Compared to existing bounds, our bound offers two significant advantages: Firstly, it does not depend on additional assumptions. Secondly, it is considerably tighter, aligning with the bounds of standard generalization. Therefore, our result provides a different perspective on understanding robust generalization: The mismatch terms between standard and robust generalization bounds shown in previous studies do not contribute to the poor robust generalization. Instead, these disparities solely due to mathematical issues. Finally, we extend the main result to adversarial robustness against general non-$\ell_p$ attacks and other neural network architectures.